//和可被 K 整除的子数组
class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) 
    {
        //同余定理 (a-b)/k=c......0 
        // -> a%k == b%k
        //所以在[0,i]区间内  (sum-某一前缀和)%k==0
        //--> sum%k == 某一前缀和%k
        unordered_map<int,int>hash;// 余数,出现次数
        hash[0%k]=1;
        int res=0;
        int sum=0;
        for(auto e:nums)
        {
            sum+=e;
            int tmp=(sum%k+k)%k;//修正后取sum的余数
            if(hash.count(tmp)) res+=hash[tmp];
            hash[tmp]++; 
        }
        return res;
    }
};